﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace TreeTraversal
{
    enum DirectionalHeapType
    { 
        Min,
        Max
    }

    class DirectionalHeap<T> : Heap<T> where T : IComparable
    {
        public override string Name
        {
            get { return m_Type.ToString() + " Heap"; }
        }

        DirectionalHeapType m_Type;

        public DirectionalHeap(DirectionalHeapType Type)
        {
            m_Type = Type;
        }

        public override BinaryTreeNode<T> Add(T Value)
        {
            BinaryTreeNode<T> addedNode = base.Add(Value);

            // cascade up
            bool Continue = true;
            int currentIndex = HeapArray.Count - 1;
            BinaryTreeNode<T> currentNode = addedNode;
            while (currentNode.Parent != null && Continue)
            {
                int parentIndex = GetParentIndex(currentIndex);
                BinaryTreeNode<T> parentNode = currentNode.Parent;
                int compareResult = parentNode.Value.CompareTo(currentNode.Value);
                if (m_Type == DirectionalHeapType.Max && compareResult < 0 ||
                    m_Type == DirectionalHeapType.Min && compareResult > 0)
                {
                    // swap them in the array
                    //HeapArray[parentIndex] = currentNode;
                    //HeapArray[currentIndex] = parentNode;
                    currentIndex = parentIndex;

                    // swap values...
                    T tempValue = parentNode.Value;
                    parentNode.Value = currentNode.Value;
                    currentNode.Value = tempValue;
                    currentNode = parentNode;

                    // adjust pointers
                    //ChildDirection direction = addedNode.GetDirection();
                    //ChildDirection parentDirection = parentNode.GetDirection();
                    //BinaryTreeNode<T> tempLeft = parentNode.Left;
                    //BinaryTreeNode<T> tempRight = parentNode.Right;
                    //int tempLeftDepth = parentNode.LeftDepth;
                    //int tempRightDepth = parentNode.RightDepth;

                    //parentNode.LeftDepth = addedNode.LeftDepth;
                    //parentNode.RightDepth = addedNode.RightDepth;
                    //addedNode.LeftDepth = tempLeftDepth;
                    //addedNode.RightDepth = tempRightDepth;

                    //addedNode.Parent = parentNode.Parent;
                    //if (parentDirection == ChildDirection.Left)
                    //{
                    //    addedNode.Parent.Left = addedNode;
                    //}
                    //else if (parentDirection == ChildDirection.Right)
                    //{
                    //    addedNode.Parent.Right = addedNode;
                    //}

                    //parentNode.Parent = addedNode;

                    //parentNode.Left = addedNode.Left;
                    //parentNode.Right = addedNode.Right;

                    //if (direction == ChildDirection.Left)
                    //{
                    //    addedNode.Left = parentNode;
                    //    addedNode.Right = tempRight;
                    //}
                    //else if (direction == ChildDirection.Right)
                    //{
                    //    addedNode.Right = parentNode;
                    //    addedNode.Left = tempLeft;
                    //}
                }
                else
                {
                    Continue = false;
                }
            }

            return currentNode;
        }
    }
}
